home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmhash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  5.2 KB  |  115 lines
  1. // CmHash.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // Hash table definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMHASH_H
  10. #define _CMHASH_H
  11.  
  12. #include <cm/include/cmcont.h>
  13.  
  14. class CmHashBucket;                            // Hash bucket class stub.
  15. class CmHashNode;                              // Hash node class stub.
  16. class CmHashTableIterator;                     // Iterator class stub.
  17.  
  18. class CmHashTable : public CmContainer {       // Hash table definition.
  19. public:
  20.   CmHashTable(unsigned = 10);                  // Default table constructor.
  21.   CmHashTable(const CmHashTable&);             // Table copy constructor.
  22.  ~CmHashTable();                               // Hash table destructor.
  23.  
  24.   CmHashTable& operator=(const CmHashTable&);  // Assignment operator.
  25.  
  26.   int         total      () const;             // Number of object in table.
  27.   Bool        add        (CmObject*);          // Add object to container.
  28.   Bool        remove     (CmObject*);          // Remove object.
  29.   CmObject*   lookup     (CmObject*) const;    // Find equal object.
  30.   Bool        contains   (CmObject*) const;    // Table has object?
  31.   unsigned    occurrences(CmObject*) const;    // Count occurrences of object.
  32.   void        removeAll  ();                   // Remove all objects.
  33.   Bool        resize     (unsigned);           // Resize the hash table.
  34.   Bool        isEmpty    () const;             // Is table empty?
  35.   CmIterator* newIterator() const;             // Get hash table iterator.
  36.  
  37.   Bool write(CmReserveFile&) const;            // Write to reserve file.
  38.   Bool read (CmReserveFile&);                  // Read from reserve file.
  39.  
  40.   CMOBJECT_DEFINE(CmHashTable, CmContainer)    // Define object funcs.
  41.  
  42. protected:
  43.   int           _total;                        // Number of objects in table.
  44.   CmHashBucket *_buckets;                      // Array of hash buckets.
  45.   friend        CmHashTableIterator;           // Iterator can access.
  46. };
  47.  
  48. class CmHashBucket {                           // Bucket class definition.
  49. protected:
  50.   CmHashBucket() : _size(0), _first(NULL), _last(NULL) {}  // Bucket construct.
  51.  ~CmHashBucket() { removeAll(FALSE); }         // Bucket destructor.
  52.  
  53.   unsigned  size     () const;                 // Return list size.
  54.   Bool      append   (CmObject*);              // Add object to end of list.
  55.   Bool      contains (CmObject*) const;        // See if object is in list.
  56.   Bool      remove   (CmObject*, Bool);        // Remove object from list.
  57.   CmObject* lookup   (CmObject*) const;        // Find equal object in list.
  58.   void      removeAll(Bool);                   // Remove all objects.
  59.  
  60.   unsigned    _size;                           // List size.
  61.   CmHashNode *_first;                          // First object in list.
  62.   CmHashNode *_last;                           // Last object in list.
  63.   friend      CmHashTable;                     // Table can access.
  64.   friend      CmHashTableIterator;             // Iterator can access.
  65. };
  66.  
  67. class CmHashNode {                             // Hash bucket node definition.
  68. protected:
  69.   CmHashNode(CmObject* O)                      // Node constructor.
  70.             : _next(NULL), _data(O) {}
  71.  
  72.   CmHashNode *_next;                           // Next node in list.
  73.   CmObject   *_data;                           // Object pointer.
  74.   friend      CmHashBucket;                    // Bucket can access.
  75.   friend      CmHashTableIterator;             // Iterator can access.
  76. };
  77.  
  78. class CmHashTableIterator : public CmIterator {  // Iterator definition.
  79. public:
  80.   CmHashTableIterator(const CmHashTable&);     // Iterator constructor.
  81.  
  82.   Bool      done    () const;                  // Check if done iterating.
  83.   CmObject* next    ();                        // Return and advance.
  84.   CmObject* previous();                        // Return and backup.
  85.   CmObject* current () const;                  // Return current object.
  86.   void      first   ();                        // Move to first object.
  87.   void      last    ();                        // Move to last object.
  88.  
  89.   CMOBJECT_DEFINE(CmHashTableIterator, CmIterator)  // Define object funcs.
  90.  
  91. protected:
  92.   const CmHashTable& _table;                   // Table being iterated.
  93.   int                _bucket;                  // Current bucket index.
  94.   CmHashNode        *_node;                    // Current bucket node.
  95.   friend             CmHashTable;              // Table class can access.
  96. };
  97.  
  98. // "total" returns the number of object contained in the table.
  99. inline int CmHashTable::total() const
  100. { return _total; }
  101.  
  102. // "size" returns the hash bucket size.
  103. inline unsigned CmHashBucket::size() const
  104. { return _size; }
  105.  
  106. // "done" checks to see if the iterator can move any farther.
  107. inline Bool CmHashTableIterator::done() const
  108. { return (_node) ? FALSE : TRUE; }
  109.  
  110. // "current" returns the current object pointed to by the iterator.
  111. inline CmObject* CmHashTableIterator::current() const
  112. { return (_node) ? _node->_data : NULL; }
  113.  
  114. #endif
  115.